package com.origin.niuke.greedy;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/6/1 22:49
 */
public class NC86 {

    public int[] findElement(int[][] mat, int n, int m, int x) {
        // write code here
        int[] ans = new int[2];
        if (n == 0 || m == 0) return ans;
        int i = n - 1, j = 0;
        while (i >= 0 && j < m) {
            if (x == mat[i][j]) {
                ans[0] = i;
                ans[1] = j;
                break;
            }
            if (x < mat[i][j]) --i;
            else ++j;
        }
        return ans;
    }

    public int[] findElement_erfen(int[][] mat, int n, int m, int x) {
        int[] ans = new int[2];
        if (n == 0 || m == 0) return ans;
        for (int i = 0; i < n; i++) {
            int l = 0, r = m - 1;
            while (l <= r) {
                int mid = l + (r - l) / 2;
                if (mat[i][mid] == x) {
                    ans[0] = i;
                    ans[1] = mid;
                }
                if (x > mat[i][mid]) l = mid + 1;
                else r = mid - 1;
            }
        }
        return ans;
    }

}
